__author__ = 'st316'
'''
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"
'''


class Solution:
    # @param an integer
    # @return a list of string
    def generateParenthesis(self, n):
        return ['(' + x for x in self.generate(1, 0, n)]

    def generate(self, i, j, n):  # i: num of ( already use,j: num of ) already use
        r = []
        if j == n:
            return r
        if i == n:
            r.extend([')' * (n - j)])
        elif i > j:
            r.extend([('(' + x) for x in self.generate(i + 1, j, n)])
            r.extend([(')' + x) for x in self.generate(i, j + 1, n)])
        elif i == j:
            r.extend([('(' + x) for x in self.generate(i + 1, j, n)])
        return r


if __name__ == '__main__':
    s = Solution()
    print s.generateParenthesis(2)

